public class Main {
    public static void main(String[] args) {
        ListNode n1 = new ListNode(3);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(0);
        ListNode n4 = new ListNode(4);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n2;
        Solution s = new Solution();
        System.out.println(s.detectCycle(n1));
    }
}


class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}


//快慢指针法
class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode fast = head.next, slow = head;
        while(fast != null && fast != slow){
            if(fast.next == null){
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        if(fast == null){
            return null;
        }

        //有环
        //设头节点到环的位置前有i个节点，环的位置到相遇位置有j个节点，相遇位置到环的位置有k个节点，则：
        //i + n(j + k) + j = 2(i + j)，需要求i
        //==> i = nj + nk - j
        //==> i = (n - 1)(j + k) + k
        ListNode fromHead = head;
        slow = slow.next;
        while(fromHead != slow){
            fromHead = fromHead.next;
            slow = slow.next;
        }
        return fromHead;
    }
}